1580B - Mathematics Curriculum - CodeForces Solution

#pragma GCC optimize "tree-vectorize"

#pragma GCC target "movbe,mmx,sse,sse2,sse3,ssse3,sse4.1,sse4.2,popcnt,avx,avx2,aes,pclmul,fsgsbase,rdrnd,fma,bmi,bmi2,f16c,rdseed,clflushopt,xsavec,xsaves,adx,prfchw,lzcnt,abm"

#include <algorithm>

#include <iostream>

#include <numeric>

#include <vector>

#include <queue>

#include <map>

#include <set>



using namespace std;



bool online_judge =

                    #ifdef ONLINE_JUDGE

                    1;

                    #else

                    0;

                    #endif

struct { using X = int; template <typename T = X> T operator()() const { T t; cin >> t; return t; } operator X() const { return operator()(); } template <typename T> operator T() const { return operator()<T>(); } template <auto=0> string operator~() const { return *this; } char operator!() const { return *this; } } $;

void print(const auto&... ts) { string sep = ""; ((cout << sep << ts, sep = " "), ...); cout << '\n'; }

void prints(const auto& c) { cout << c.end() - c.begin() << ' ' << c << '\n'; }

auto operator>>(istream& in, auto&& c) -> enable_if_t<!is_same_v<decay_t<decltype(c.begin(), c)>, string>, decltype(in)> { for (auto& i: c) in >> i; return in; }

auto operator<<(ostream& out, const auto& c) -> enable_if_t<!is_same_v<decay_t<decltype(c.begin(), c)>, string>, decltype(out)> { string sep = ""; for (auto i: c) out << sep << i, sep = " "; return out; }

auto operator>>(istream& in, auto&& p) -> decltype(p.first, p.second, in) { return in >> p.first >> p.second; }

auto operator<<(ostream& out, const auto& p) -> decltype(p.first, p.second, out) { return out << p.first << ' ' << p.second; }

template <typename It> struct range { It first, last; constexpr range() {} constexpr range(It first, It last) : first{first}, last{last} {} constexpr range(It first, auto n) : range{first, first + n} {} constexpr range(auto&& c) : range{c.begin(), c.end()} {} constexpr It begin() const { return first; } constexpr It end() const { return last; } constexpr int size() const { return last - first; } constexpr const auto& operator[](int i) const { return first[i]; } constexpr auto& operator[](int i) { return first[i]; } }; range(auto&& c) -> range<decltype(c.begin())>;

template <int from, int which> auto getfield(const auto& a) -> const auto& { static_assert(1 <= which && which <= from && from <= 5); auto fix = [](auto& x) -> auto& { return x; }; if constexpr (from == 1) { auto& [a1] = a; if constexpr (which == 1) return fix(a1); } else if constexpr (from == 2) { auto& [a1, a2] = a; if constexpr (which == 1) return fix(a1); if constexpr (which == 2) return fix(a2); } else if constexpr (from == 3) { auto& [a1, a2, a3] = a; if constexpr (which == 1) return fix(a1); if constexpr (which == 2) return fix(a2); if constexpr (which == 3) return fix(a3); } else if constexpr (from == 4) { auto& [a1, a2, a3, a4] = a; if constexpr (which == 1) return fix(a1); if constexpr (which == 2) return fix(a2); if constexpr (which == 3) return fix(a3); if constexpr (which == 4) return fix(a4); } else if constexpr (from == 5) { auto& [a1, a2, a3, a4, a5] = a; if constexpr (which == 1) return fix(a1); if constexpr (which == 2) return fix(a2); if constexpr (which == 3) return fix(a3); if constexpr (which == 4) return fix(a4); if constexpr (which == 5) return fix(a5); } }

template <int from, int which, typename Cmp = equal_to<>> struct CompareField { bool operator()(const auto& a, const auto& b) const { return Cmp{}(getfield<from, which>(a), getfield<from, which>(b)); } };

template <int from, int which, int... whichs> struct Ordering { bool operator()(const auto& a, const auto& b) const { auto& aa = getfield<from, labs(which)>(a), & bb = getfield<from, labs(which)>(b); if (aa < bb) { return which > 0; } else if (bb < aa) { return which < 0; } else if constexpr (sizeof...(whichs)) { return Ordering<from, whichs...>{}(a, b); } return 0; } };

bool minb(auto& a, const auto& b) { return b < a? a = b, 1: 0; } auto& mini(auto& a, const auto& b) { return minb(a, b), a; } auto mind(auto& a, const auto& b) { auto t = a; return t - mini(a, b); }

bool maxb(auto& a, const auto& b) { return a < b? a = b, 1: 0; } auto& maxi(auto& a, const auto& b) { return maxb(a, b), a; } auto maxd(auto& a, const auto& b) { auto t = a; return maxi(a, b) - t; }

auto unz(auto a) { return max(a, {}); } int sgn(auto a) { return (0 < a) - (a < 0); } auto change(auto& a, const auto& b) { auto t = a; return (a = b) - t; }

void lshift(auto& first, auto& second, auto&... args) { first = second; if constexpr (sizeof...(args)) lshift(second, args...); } void rshift(auto& first, auto& second, auto&... args) { if constexpr (sizeof...(args)) rshift(second, args...); second = first; }

void lrotate(auto& arg, auto&... args) { auto t = arg; lshift(arg, args...); ([](auto&t)->auto&{return t;}(args), ...) = t; } void rrotate(auto& arg, auto&... args) { auto t = ([](auto&t)->auto&{return t;}(args), ...); rshift(arg, args...); arg = t; }

template <typename T, typename Cmp = greater<>> using PQ = priority_queue<T, vector<T>, Cmp>;



constexpr int N = 1e2 + 1;

int a[N][N][44];

int mxk[N][N];

int cnk[N][N];

uint64_t buf[N];



int main() {

  cin.tie(0)->sync_with_stdio(!online_judge);

  ios::sync_with_stdio(0);

  int n = $, m = $, k = $, p = $;

  for (int i = 0; i <= n; ++i)

  for (int j = 0; j <= i; ++j) {

    cnk[i][j] = !i || !j || j == i? 1: (cnk[i - 1][j] + cnk[i - 1][j - 1]) % p;

  }

  auto fma = [p](auto&& a, int b, int c) { return a = (a + b * (uint64_t)c) % p; };

  for (int j = 0; j <= m; ++j) {

    a[0][j][0] = 1;

  }

  for (int i = 1, f = 1; f = fma(0, f, i), i <= n; ++i)

  for (int j = unz(m - n + i); j <= m; ++j) {

    if (j == 0 || j > i) {

      a[i][j][0] = f;

      continue;

    }

    int cmk = 0;

    for (int i0 = 0; i0 * 2 < i; ++i0) {

      int i1 = i - i0 - 1, jj = j - 1, ccmk = mxk[i0][jj] + mxk[i1][jj];

      maxi(cmk, ccmk);

      int coef = fma(0, 1 + (i0 != i1), cnk[i - 1][i0]);

      fill_n(buf, ccmk + 1, 0);

      for (int k0 = 0; k0 <= mxk[i0][jj]; ++k0) {

        if (k0 && k0 % 18 == 0) {

          for (int k = k0 - 18; k < k0 + mxk[i1][jj]; ++k) {

            buf[k] %= p;

            if (++k < k0 + mxk[i1][jj]) buf[k] %= p;

            if (++k < k0 + mxk[i1][jj]) buf[k] %= p;

            if (++k < k0 + mxk[i1][jj]) buf[k] %= p;

          }

        }

        for (int k1 = 0; k1 <= mxk[i1][jj]; ++k1) {

          buf[k0 + k1] += a[i0][jj][k0] * (uint64_t)a[i1][jj][k1];

        }

      }

      for (int k0 = mxk[i0][jj], k = k0 - k0 % 18; k <= k0 + mxk[i1][jj]; ++k) {

        buf[k] %= p;

        if (++k <= k0 + mxk[i1][jj]) buf[k] %= p;

        if (++k <= k0 + mxk[i1][jj]) buf[k] %= p;

        if (++k <= k0 + mxk[i1][jj]) buf[k] %= p;

      }

      for (int k = 0; k <= ccmk; ++k) {

        fma(a[i][j][k + (j == 1)], buf[k], coef);

        if (++k <= ccmk) fma(a[i][j][k + (j == 1)], buf[k], coef);

        if (++k <= ccmk) fma(a[i][j][k + (j == 1)], buf[k], coef);

        if (++k <= ccmk) fma(a[i][j][k + (j == 1)], buf[k], coef);

      }

    }

    mxk[i][j] = cmk + (j == 1);

  }

  print(a[n][m][min(k, (int)size(**a) - 1)]);

}